package algorithm.sort;

import java.util.Arrays;

/**
 * @ Author     ：wangyw
 * @ Date       ：Created in 下午5:38 2021/11/2
 * @ Description：归并排序
 */
public class _04MergeSort implements SortAlgrithm {

    @Override
    public <T extends Comparable<T>> T[] sort(T[] unsorted) {
        doSort(unsorted, 0, unsorted.length - 1);
        return unsorted;
    }

    public <T extends Comparable<T>> void doSort(T[] arr, int l, int r) {
        if (l < r) {
            int mid = l + ((r - l) >> 1);
            doSort(arr, l, mid);
            doSort(arr, mid + 1, r);
            merge(arr, l, mid, r);
        }
    }

    public static <T extends Comparable<T>> void merge(T[] arr, int l, int mid, int r) {
        int len = r - l + 1;
        T[] helper = (T[]) new Comparable[len];
        int p1 = l, p2 = mid + 1, i = 0;
        while (p1 <= mid && p2 <= r) {
            if (arr[p1].compareTo(arr[p2]) < 0) {
                helper[i++] = arr[p1++];
            } else {
                helper[i++] = arr[p2++];
            }
        }
        while (p1 <= mid) {
            helper[i++] = arr[p1++];
        }
        while (p2 <= r) {
            helper[i++] = arr[p2++];
        }
        for (int j = 0; j < len; j++) {
            arr[l + j] = helper[j];
        }
    }

    public static void main(String[] args) {
        Integer[] randomIntArr = SortUtils.getRandomIntArr(15, 100);
        System.out.println(Arrays.toString(randomIntArr));
        new _04MergeSort().sort(randomIntArr);
        System.out.println(Arrays.toString(randomIntArr));
    }
}
